package basic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//一个 平方和三元组 (a,b,c) 指的是满足 a2 + b2 = c2 的 整数 三元组 a，b 和 c 。
//
//        给你一个整数 n ，请你返回满足 1 <= a, b, c <= n 的 平方和三元组 的数目。
public class basic1925 {

    public int countTriples1(int n) {
//想的太简单了
//        int i = 5;
//        int count=0;
//        while (i <= n) {
//            i=i+5;
//            count=count+1;
//        }
//        return count*2;
        int ans=0;
        int[] a=new int[n*n+1];
        for(int i=1;i<=n;i++)a[i*i]=1;
        for(int c=1;c<=n;c++){
            for(int b=1;b<c;b++)
                ans+=a[c*c-b*b];
        }
        return ans;

        //这个方法比较妙 难以想出
    }

//
//    public int countTriples1(int n) {
//        int cnt = 0;
//        for (int i = 1; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                for (int k = j + 1; k <= n; k++) {
//                    if (i * i + j * j == k * k) {
//                        cnt++;
//                    }
//                }
//            }
//        }
//        return cnt * 2;
//    }

//  CKG TODO 2023/5/12: 这里本来写的是List  但是ｐａｔｈ　竟然没有ｒｅｍｏｖｅＬａｓｔ方法
  LinkedList<Integer> path= new LinkedList<Integer>();
    List<List<Integer>>  result=new ArrayList<>();
    public int countTriples(int n) {
        backTrack(1,n);
        return  result.size();
    }

    public  void backTrack(int start,int n){
        if (path.size()>3){
            return;
        }
        if (path.size()==3){
            Integer a1=path.get(0);
            Integer b1=path.get(1);
            Integer c1=path.get(2);
            int a=a1.intValue();
            int b=b1.intValue();
            int c=c1.intValue();
            if (c*c==a*a+b*b){
                result.add(new ArrayList<>(path));
            }
        }

        for (int i = 1; i <=n ; i++) {
            path.add(i);
            backTrack(i+1,n);
            path.removeLast();
        }

    }

    public static void main(String[] args) {
        basic1925 basic1925 = new basic1925();
        System.out.println(basic1925.countTriples(5));
    }

}
